---
title: "（50分 多路归并 二分）技能升级"
created: 2025-11-28
tags:
  - 算法
---

# （50分 多路归并 二分）技能升级

## 题目  [技能升级](https://www.acwing.com/problem/content/4659/)

![[image-dd6f2faa.png]]

## 思路分析

每次加点提升最多的 用大根堆维护

拿到了一半的分 知足了 （前年py b组第8题）

```cpp
#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;
priority_queue<PII> heap;
int n,m;

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++){
        int a,b;cin>>a>>b;
        heap.push({a,b});
    }
    int res=0;
    while(m--){
        int addval=heap.top().first;
        int delval=heap.top().second;
        int nextaddval=heap.top().first-delval;

        heap.pop();

        res+=addval;
        heap.push({nextaddval,delval});
    }
    cout<<res;
    return 0;
}
```

![[image-f94fd5f1.png]]

我草 本来就是听听看 发现好像又悟到了什么 一开始以为什么是多路归并呢 慌得一批

我说听着这个思路怎么这么耳熟 原来之前已经接触过：蚯蚓

可以开多个优先队列 对头元素一定是这一路里最大的 那么只需要在多个对头中选一个最大的即可

本质是以空间换时间

看来又能整理出一类问题了 多路归并

但这道题……emm 暂时放一下 后面的二分没看懂怎么来的 分心了

## 代码实现

```

```

## 同类题型

## 视频讲解

---
⬅️ [[砍竹子|砍竹子]] 🏠 [[00-刷题理模型]] ➡️ [[（70分 dp+贪心）倍数问题|（70分 dp+贪心）倍数问题]]